Approximate Shortest Paths in Simple Polyhedra
Identifieur interne : 002755 ( Main/Exploration ); précédent : 002754; suivant : 002756Approximate Shortest Paths in Simple Polyhedra
Auteurs : Fajie Li [République populaire de Chine] ; Reinhard Klette [Nouvelle-Zélande]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: Since the pioneering work by (Cohen and Kimmel, 1997) on finding a contour as a minimal path between two end points, shortest paths in volume images have raised interest in computer vision and image analysis. This paper considers the calculation of a Euclidean shortest path (ESP) in a three-dimensional (3D) polyhedral space Π. We propose an approximate $\kappa(\varepsilon) \cdot {\cal O}(M|V|)$ 3D ESP algorithm, not counting time for preprocessing. The preprocessing time complexity equals ${\cal O}(M|E| + |{\cal F}| + |V|\log|V|)$ for solving a special, but ‘fairly general’ case of the 3D ESP problem, where Π does not need to be convex. V and E are the sets of vertices and edges of Π, respectively, and ${\cal F}$ is the set of faces (triangles) of Π. M is the maximal number of vertices of a so-called critical polygon, and κ(ε) = (L 0 − L)/ε where L 0 is the length of an initial path and L is the true (i.e., optimum) path length. The given algorithm solves approximately three (previously known to be) NP-complete or NP-hard 3D ESP problems in time $\kappa(\varepsilon) \cdot {\cal O}(k)$ , where k is the number of layers in a stack, which is introduced in this paper as being the problem environment. The proposed approximation method has straightforward applications for ESP problems when analyzing polyhedral objects (e.g., in 3D imaging), of for ‘flying’ over a polyhedral terrain.
Url:
DOI: 10.1007/978-3-642-19867-0_43
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 003528
- to stream Istex, to step Curation: 003486
- to stream Istex, to step Checkpoint: 000655
- to stream Main, to step Merge: 002797
- to stream Main, to step Curation: 002755
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Approximate Shortest Paths in Simple Polyhedra</title><author><name sortKey="Li, Fajie" sort="Li, Fajie" uniqKey="Li F" first="Fajie" last="Li">Fajie Li</name></author><author><name sortKey="Klette, Reinhard" sort="Klette, Reinhard" uniqKey="Klette R" first="Reinhard" last="Klette">Reinhard Klette</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:DF74ED3909A698AF5A5A56F518BBD59186ECA1BB</idno><date when="2011" year="2011">2011</date><idno type="doi">10.1007/978-3-642-19867-0_43</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-2MS8QQ6N-C/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">003528</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003528</idno><idno type="wicri:Area/Istex/Curation">003486</idno><idno type="wicri:Area/Istex/Checkpoint">000655</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000655</idno><idno type="wicri:doubleKey">0302-9743:2011:Li F:approximate:shortest:paths</idno><idno type="wicri:Area/Main/Merge">002797</idno><idno type="wicri:Area/Main/Curation">002755</idno><idno type="wicri:Area/Main/Exploration">002755</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Approximate Shortest Paths in Simple Polyhedra</title><author><name sortKey="Li, Fajie" sort="Li, Fajie" uniqKey="Li F" first="Fajie" last="Li">Fajie Li</name><affiliation wicri:level="1"><country xml:lang="fr">République populaire de Chine</country><wicri:regionArea>College of Computer Science and Technology, Huaqiao University, Xiamen, Fujian</wicri:regionArea><wicri:noRegion>Fujian</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">République populaire de Chine</country></affiliation></author><author><name sortKey="Klette, Reinhard" sort="Klette, Reinhard" uniqKey="Klette R" first="Reinhard" last="Klette">Reinhard Klette</name><affiliation wicri:level="1"><country xml:lang="fr">Nouvelle-Zélande</country><wicri:regionArea>Computer Science Department, The University of Auckland, Private Bag 92019, 1142, Auckland</wicri:regionArea><wicri:noRegion>Auckland</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Nouvelle-Zélande</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Since the pioneering work by (Cohen and Kimmel, 1997) on finding a contour as a minimal path between two end points, shortest paths in volume images have raised interest in computer vision and image analysis. This paper considers the calculation of a Euclidean shortest path (ESP) in a three-dimensional (3D) polyhedral space Π. We propose an approximate $\kappa(\varepsilon) \cdot {\cal O}(M|V|)$ 3D ESP algorithm, not counting time for preprocessing. The preprocessing time complexity equals ${\cal O}(M|E| + |{\cal F}| + |V|\log|V|)$ for solving a special, but ‘fairly general’ case of the 3D ESP problem, where Π does not need to be convex. V and E are the sets of vertices and edges of Π, respectively, and ${\cal F}$ is the set of faces (triangles) of Π. M is the maximal number of vertices of a so-called critical polygon, and κ(ε) = (L 0 − L)/ε where L 0 is the length of an initial path and L is the true (i.e., optimum) path length. The given algorithm solves approximately three (previously known to be) NP-complete or NP-hard 3D ESP problems in time $\kappa(\varepsilon) \cdot {\cal O}(k)$ , where k is the number of layers in a stack, which is introduced in this paper as being the problem environment. The proposed approximation method has straightforward applications for ESP problems when analyzing polyhedral objects (e.g., in 3D imaging), of for ‘flying’ over a polyhedral terrain.</div></front></TEI><affiliations><list><country><li>Nouvelle-Zélande</li><li>République populaire de Chine</li></country></list><tree><country name="République populaire de Chine"><noRegion><name sortKey="Li, Fajie" sort="Li, Fajie" uniqKey="Li F" first="Fajie" last="Li">Fajie Li</name></noRegion><name sortKey="Li, Fajie" sort="Li, Fajie" uniqKey="Li F" first="Fajie" last="Li">Fajie Li</name></country><country name="Nouvelle-Zélande"><noRegion><name sortKey="Klette, Reinhard" sort="Klette, Reinhard" uniqKey="Klette R" first="Reinhard" last="Klette">Reinhard Klette</name></noRegion><name sortKey="Klette, Reinhard" sort="Klette, Reinhard" uniqKey="Klette R" first="Reinhard" last="Klette">Reinhard Klette</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002755 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002755 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:DF74ED3909A698AF5A5A56F518BBD59186ECA1BB
|texte= Approximate Shortest Paths in Simple Polyhedra
}}
| This area was generated with Dilib version V0.6.33. |  |